package top.jolyoulu.力扣._1641_统计字典序元音字符串的数目;
//给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。
//
// 字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。
//
//
//
// 示例 1：
//
//
//输入：n = 1
//输出：5
//解释：仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]
//
//
// 示例 2：
//
//
//输入：n = 2
//输出：15
//解释：仅由元音组成的 15 个字典序字符串为
//["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
//注意，"ea" 不是符合题意的字符串，因为 'e' 在字母表中的位置比 'a' 靠后
//
//
// 示例 3：
//
//
//输入：n = 33
//输出：66045
//
//
//
//
// 提示：
//
//
// 1 <= n <= 50
//
//
// Related Topics 数学 动态规划 组合数学 👍 94 👎 0

import top.jolyoulu.utils.TimerUtils;

//leetcode submit region begin(Prohibit modification and deletion)
public class Answer1 {
    /*
        思路：首先找规律，现在有["a","e","i","o","u"]
        当n=1时，从左往右开始组合
        a
        e
        i
        o
        u
        共有 1+1+1+1+1 = 5种组合
        当n=2时，从左往右开始组合
        aa              = 1
        ee ea           = 2
        ii ie ia        = 3
        oo oi oe oa     = 4
        uu uo ui ue ua  = 5
        共有 1+2+3+4+5 = 15种组合
        通过观察当n的2个时，a只能和a组合，e可以和a、e组合，i可以和a、e、i组合
        a的组合数 = a;
        e的组合数 = a的组合数 + e;
        i的组合数 = a的组合数 + e的组合数 + i;
        o的组合数 = a的组合数 + e的组合数 + i的组合数 + o;
        u的组合数 = a的组合数 + e的组合数 + i的组合数 + o的组合数 + u;
        结果 = a的组合数 + e的组合数 + i的组合数 + o的组合数 + u的组合数
    */
    class Solution {
        public int countVowelStrings(int n) {
            int a = 1, e = 1, i = 1, o = 1, u = 1;
            for (int j = 0; j < n; j++) {
                e += a;
                i += e;
                o += i;
                u += o;
            }
            return u;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Answer1().new Solution();
        System.out.println("用例1=======================================");
        System.out.println("n = 1");
        TimerUtils.timer(() -> {
            System.out.println(solution.countVowelStrings(1));
        });
        System.out.println("用例2=======================================");
        System.out.println("n = 2");
        TimerUtils.timer(() -> {
            System.out.println(solution.countVowelStrings(2));
        });
    }
}
//leetcode submit region end(Prohibit modification and deletion)